import java.util.Scanner;
class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        char[] arr = s.toCharArray();
        //1.建表
        int[] dp = new int[len];
        //2.初始化
        if(arr[0] - '0' != 0) {
            dp[0] = 1;
        }
        //边界问题
        if(len == 1) {
            return dp[0];
        }
        int tmp = (arr[0] - '0')*10 + arr[1] - '0';
        if(arr[0] != '0' && arr[1] != '0') {
            dp[1] +=1;
        }
        if(tmp > 9 && tmp < 27) {
            dp[1] += 1;
        }
        //3.填表
        for(int i = 2;i < len;i++) {
            if((arr[i] -'0') != 0) {
                dp[i] += dp[i-1];
            }
            int a = (arr[i-1] - '0')*10 + arr[i] - '0';
            if(a > 9 && a < 27) {
                dp[i] += dp[i-2];
            }
        }
        return dp[len-1];
    }
}
